﻿using System;
using System.Collections.Generic;

namespace ProblemsSet
{
    public class Problem_104 : BaseProblem
    {
        public override object GetResult()
        {

            long frstL = 1;
            long secL = 1;
            long curL = 1;
            double frstF = 1;
            double secF = 1;
            double curF = 1;
            long res = 2;
            var isFrs = true;
            while (true)
            {
                res++;
                curF = frstF + secF;
                curL = frstL + secL;
                if (isFrs)
                {
                    secF = curF;
                    secL = curL;
                    isFrs = false;
                }
                else
                {
                    frstF = curF;
                    frstL = curL;
                    isFrs = true;
                }
                if (IsFirst(curF) && IsLast(curL))
                    return res;
                if (frstF > 10000000000)
                {
                    frstF /= 100000;
                    secF /= 100000;
                }
                if (frstL <= 1000000000) continue;
                frstL %= 1000000000;
                secL %= 1000000000;
            }

        }

        private static bool IsFirst(double st)
        {
            var s = st.ToString().Replace(".", "");
            s = s.Replace(",", "");
            var hsb = new HashSet<char>();
            if (s.Length < 9) return false;
            for (var i = 0; i < 9; i++)
            {
                if (s[i] == '0' || hsb.Contains(s[i])) return false;
                hsb.Add(s[i]);
            }
            return true;
        }

        private static bool IsLast(double st)
        {
            var s = st.ToString().Replace(".", "");
            s = s.Replace(",", "");
            var hse = new HashSet<char>();
            if (s.Length < 9) return false;
            for (var i = 0; i < 9; i++)
            {
                if (s[s.Length - 1 - i] == '0' || hse.Contains(s[s.Length - 1 - i])) return false;
                hse.Add(s[s.Length - 1 - i]);
            }
            return true;
        }

        public override string Problem
        {
            get
            {
                return @"The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn1 + Fn2, where F1 = 1 and F2 = 1.
It turns out that F541, which contains 113 digits, is the first Fibonacci number for which the last nine digits are 1-9 pandigital (contain all the digits 1 to 9, but not necessarily in order). And F2749, which contains 575 digits, is the first Fibonacci number for which the first nine digits are 1-9 pandigital.

Given that Fk is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find k.";
            }
        }

        public override bool IsSolved
        {
            get
            {
                return true;
            }
        }

        public override object Answer
        {
            get
            {
                return 329468;
            }
        }
    }
}
